package com.base.leetcode;

import com.base.dataStructure.Tree.TreeNode;

/**
 * @Author: hdhao
 * @Create: 2023/4/9 - 15:41
 * @Version: v1.0
 */
//求二叉搜索树最近公共祖先(祖先也包括自己)
public class Leetcode235 {
    /*
        待查找节点 p q 在某一节点的两侧,那么此节点就是最近的公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode a = root;
        while ((p.val < a.val && q.val < a.val) || (a.val < p.val && a.val < q.val)) {
            //在同一侧
            if (p.val < a.val) {
                a = a.left;
            } else {
                a = a.right;
            }
        }
        return a;
    }
}
